/*
 * @lc app=leetcode.cn id=315 lang=typescript
 *
 * [315] 计算右侧小于当前元素的个数
 */

// @lc code=start
function countSmaller(nums: number[]): number[] {
  const size = nums.length;

  if (size === 0) return [];

  const temp = new Array(size);
  const mergeSort = (arr: number[][], l: number, r: number): void => {
    if (l >= r) return;
    let mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    let k = l;
    let i = l;
    let j = mid + 1;
    // 降序排序
    while (i <= mid || j <= r) {
      // 合并的时候都是有序状态，所以右区间剩余的就是小于当前元素的
      if (j > r || (i <= mid && arr[i][0] > arr[j][0])) {
        temp[k] = arr[i];
        arr[i][2] += r - j + 1;
        k++, i++;
      } else {
        temp[k] = arr[j];
        k++, j++;
      }
    }
    for (let i = l; i <= r; i++) {
      arr[i] = temp[i];
    }
  };

  const arr = [];
  // 将元素、下标和统计的元素个数生成新数组
  for (let i = 0; i < size; i++) {
    arr.push([nums[i], i, 0]);
  }

  mergeSort(arr, 0, size - 1);

  const result = new Array(size);
  // 生成结果
  for (let i = 0; i < size; i++) {
    result[arr[i][1]] = arr[i][2];
  }

  return result;
}
// @lc code=end
